Step 4: Printing the Output

The algorithm is done! `dist` and `parent` are now populated. We just need to loop from 0 to `V-1` and print the results.

Guidance for Step 4

  • Loop `i` from `0` to `V-1`.
  • Case 1 (Source): If `i == S`, print `0 -1`.
  • Case 2 (Unreachable): If `dist[i]` is still `float('inf')`, print `-1 -1`.
  • Case 3 (Reachable):
    • This is the tricky part! You need to find the "next hop".
    • Start at `curr = i`.
    • Use a `while` loop to trace backwards: As long as `parent[curr]` is *not* the source `S`, keep going up the chain: `curr = parent[curr]`.
    • When the loop finishes, `curr` will be the node that `S` connects to on the path to `i`. This is the next hop!
# 4. Process and Print Output
for i in range(V):
    
    # Case 1: The node is the source
    if i == S:
        print("0 -1")
    
    # Case 2: The node is unreachable
    elif dist[i] == ______:
        print("-1 -1")
        
    # Case 3: Find the "next hop"
    else:
        curr = i
        
        # Trace backwards using the parent array
        # Stop when the *parent* is the source
        while parent[curr] != ______:
            curr = parent[______]
            
        # 'curr' is now the next hop
        print(f"{dist[i]} {curr}")
Copied!